A software lock is a mechanism to allow one software thread to execute a block of code, while excluding all other threads from simultaneously executing that same block of code. The thread permitted to execute the code is said to ‘possess’ the lock, and the block of code is known as a synchronised block. Locks are employed to ensure deterministic program behaviour, a characteristic of thread safety, for synchronised blocks which are shared between threads. A compromise for this provision of thread safety is increased overhead in lock processing. Firstly, locking serialises parts of the code which reduces the potential for a program to run efficiently on multiprocessor (MP) machines. For instance, one or more processors may be blocked from entering a block of code (and hence from doing any work) while a thread possessing the lock executes the synchronised block. This is called contention. Secondly, the operation associated with locking has a high overhead, especially when there is no actual contention. In this situation, locking is required due to a possibility of contention, although contention may not actually exist.
Two categories of lock are employed: a “lightweight lock”; and a “heavyweight lock”. Lightweight locks avoid high overhead when there is no contention, but perform poorly when there is contention. Lightweight locks are usually implemented using one or more primitive machine instructions and are strongly associated with good hardware support. Heavyweight locks have relatively high overhead when there is no contention, but perform very well when there is contention. Heavyweight locks are often implemented in software, such as through a call to a thread library, kernel, or operating system, and are supported more by algorithms such as queues and schedulers rather than hardware. The heavyweight lock requires significantly greater memory storage, and many more machine operations.
In some software a software lock has a bimodal existence between a lightweight mode and a heavyweight mode. Bimodal existence of locks is explored in detail in the paper “A Study of Locking Objects with Bimodal Fields” (Tamiya Onodera and Kiyokuni Kawachiya, 1999). Initially, the lock is stored as a lightweight lock. When contention occurs, the lock is changed to a heavyweight lock. This change of mode from lightweight to heavyweight is known as lock inflation. The reverse transition, deflation from a heavyweight to a lightweight mode, occurs when certain conditions are satisfied. One of these conditions is that the lock is no longer contended. The process of inflation and deflation allows the best of both worlds: when the lock is inflated it performs well when there is contention; and when it is deflated it performs well when there is no contention.
Typically, deflation will occur as soon as a lock ceases to be contended. This is known as quick-deflation because the deflation occurs at the first opportunity in the absence of further contention. This can be effective where contention is infrequent, but a high frequency of changes between contended and uncontended periods for a lock (intermittent contention) can result in a corresponding high frequency of inflation and deflation of the lock. Intermittency is a chaotic phenomenon whereby periods of one state are punctuated by periods of another state. This may be seen on the small scale, where locks change state frequently between contended and uncontended states, which we call intermittent contention, or on the large scale where long periods of high contention are mixed with long periods of no contention, and also with periods of intermittent contention. A lock that exhibits periods of no contention, high contention, and intermittent contention is referred to as an intermittent lock. Inflation is a relatively expensive process (having a large overhead) and frequent inflation is itself a cause of poor performance in a running software application. Thus intermittent contention causes quick-deflation to be an inefficient algorithm because it causes frequent inflation.
For this reason, software can implement a modification to the quick-deflation policy in which, for each lock, a count is maintained of a number of times that the lock is inflated. When this count exceeds a threshold the lock is prevented from being deflated forever more. This is known as ‘sticky’ inflation. Thus an intermittent lock will eventually become inflated and stay inflated, but for a non-intermittent lock (i.e. a lock which is either contended or uncontended, but not both) the bimodal behaviour of inflation and deflation ensures that the lock is in an appropriate mode. Sticky inflation resolves the problem of high frequency inflation due to intermittent contention, however an intermittent lock is not fully optimised once sticky inflation has taken place because there is no opportunity to deflate the lock in the event that the lock ceases to demonstrate intermittent contention. Intermittent locks can experience highly chaotic behaviour: sometimes uncontended; sometimes contended; and sometimes intermittent. During intermittent periods it will be best for the lock to be either inflated or deflated depending on the degree of contention. During the uncontended periods, it will be best for the lock to be deflated. During the contended periods it will be best for the lock to be inflated. However the sticky inflation policy does not take into account these situations.
An improvement to sticky inflation is available which resets the inflation count to zero after a certain period. Whilst this can remove the drawback of sticky inflation after the certain period, a definition of the appropriate period is difficult to arrive at. For example a count can be reset after each execution of a Garbage Collector routine for the disposal of unused software entities, such as objects. However, there is no formal relationship between the behaviour of a lock and occurrences of garbage collection. Furthermore there is no good criterion for deciding when a lock's inflation count should be reset. Sticky inflation with such an improvement also necessitates two parameters: a parameter to determine when inflation should be sticky; and a threshold parameter to determine when deflation should occur.
This it would be advantageous to provide a scheme for the inflation and deflation of locks which provides for intermittent locks remaining bimodal, allowing them to be inflated when contended and deflated when uncontended, and further allowing for locks to remain either inflated or deflated depending on a degree of contention when the contention is intermittent.